The Fibonacci Spiral¶
- An approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling
We can see this in the sunflower, for example:¶
def fib(n: int) -> int:
if n == 1:
return(1)
elif n == 0:
return(0)
else:
return(fib(n-1)+fib(n-2))
fib(6)
https://www.mathsisfun.com/games/towerofhanoi.html
Also called the Tower of Brahma
The Towers of Hanoi actually have very little to do with the city of Hanoi in present day Vietnam.
The earliest recorded reference is from Édouard Lucas (in Récréations Mathématiques, Vol. 3, pp. 55–59, Gauthier-Villars, Paris, 1893)..
- ..who reports that there is in the temple of Kashi Vishwanath in Varanasi, Uttar Pradesh, India, a set of 64 gold disks on 3 diamond needles called the Tower of Brahma which monks have been trying to solve since the beginning of time.
Home work! :-P¶
Write a recursive programme to solve the Tower of Brahma.
Write an iterative programme to solve the Tower of Brahma.
Tower of Brahma - 2 Discs¶
Solution
- Move Disc 1 from Source to Intermediate
- Move Disc 2 from Source to Destination
- Move Disc 1 from Intermediate to Destination
Tower of Brahma - 2 Discs¶
Solution
- Move Disc 1 from Source to Intermediate
- Move Disc 2 from Source to Destination
- Move Disc 1 from Intermediate to Destination
Write this in terms of the base case (1 Disc)
Tower of Brahma - 2 Discs¶
Write this in terms of the base case (1 Disc)
- Call Disc 1 solution for the first disc with Intermediate and Destination interchanged
- tbrahma(1,s,d,i)
- Call Disc 1 solution for the second disc
- tbrahma(2,s,i,d)
- Call Disc 1 solution for the first disc
- tbrahma(1,i,s,d)
Tower of Brahma¶
Tower of Brahma¶
Solution
- Move 2 discs from Source to Intermediate
- Move Disc 3 from Source to Destination
- Move 2 discs from Intermediate to Destination
Why recursion?¶
Recursive thinking is important in programming
- It helps break down big problems into smaller ones
- Let's the machine do all the work! :-)
Sometimes, it is easier to understand the recursive solution to a problem compared to the iterative one.
At times, the recursive implementation may not be as efficient as the iterative one.
def ifact(n):
assert n >= 0 and int(n) == n, 'positive integers only!'
ans = 1
for i in range(n):
ans = ans * (i+1)
return(ans)
def rfact(n):
assert n >= 0 and int(n) == n, 'positive integers only!'
if n == 0 or n == 1:
return 1
return(n * rfact(n-1))
%timeit ifact(2500)
%timeit rfact(2500)
# compute y = $x^n$ using iteration
def iexp(x,n):
assert n >= 0 and int(n) == n, 'bad input'
y = 1
if n == 0:
return 1
for i in range(n):
#print(i+1)
y = y*x
return(y)
# compute y = $x^n$ using recursion
def r2exp(x,n):
assert n >= 0 and int(n) == n, 'n must be a positive integer'
if n == 0:
return 1
#print(x,n)
result = r2exp(x*x,n//2)
if n % 2 == 0:
return(result)
else:
return(x*result)
# compute y = $x^n$ using recursion
def r3exp(x,n):
assert n >= 0 and int(n) == n, 'n must be a positive integer'
if n == 0:
return 1
if n == 1:
return (x)
if n == 2:
return(x*x)
#print(x,n)
result = r3exp(x*x*x,n//3)
rem = n % 3
if rem == 0:
return(result)
elif rem == 1:
return(x*result)
else:
return(x*x*result)
iexp(3,4)
rexp(3,4)